package Hot100;

/**
 * @author zhangmin
 * @create 2021-12-30 16:59
 */
public class maxProduct152 {

    /**
     * 152. 乘积最大子数组
     * 给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
     * dpmax[i]表示以i为结尾的最大子数组乘积
     * dpmin[i]表示以i为结尾的最小乘积数组
     * */
    public int maxProduct(int[] nums) {
        int n=nums.length;
        if (n==1) return nums[0];
        int[] dpmax=new int[n];
        int[] dpmin=new int[n];
        dpmax[0]=nums[0];
        dpmin[0]=nums[0];
        int res=nums[0];
        for (int i = 1; i < n; i++) {
            dpmax[i]=Math.max(dpmax[i-1]*nums[i],Math.max(nums[i],dpmin[i-1]*nums[i]));
            dpmin[i]=Math.min(dpmin[i-1]*nums[i],Math.min(nums[i],dpmax[i-1]*nums[i]));
            res=Math.max(res,dpmax[i]);
        }
        return res;
    }
}
